# Definition for a binary tree node.

from typing import List
import collections
import queue


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        """
        层序遍历
        :param root:
        :return:
        """
        if not root:
            return []
        res, q = [], queue.Queue()
        q.put(root)
        while not q.empty():
            temp = []
            n = q.qsize()
            for _ in range(n):
                node = q.get()
                temp.append(node.val)
                if node.left:
                    q.put(node.left)
                if node.right:
                    q.put(node.right)
            res.append(temp)
        return res


class Solution2:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        res, q = [], collections.deque()
        q.append(root)
        while q:
            tmp = []
            for _ in range(len(q)):
                node = q.popleft()
                tmp.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            res.append(tmp)
        return res


if __name__ == '__main__':
    n1 = TreeNode(3)
    n2 = TreeNode(9)
    n3 = TreeNode(20)
    n4 = TreeNode(15)
    n5 = TreeNode(7)
    n1.left = n2
    n1.right = n3
    n3.left = n4
    n3.right = n5
    sol = Solution()
    ans = sol.levelOrder(n1)
    for x in ans:
        for y in x:
            print(y)
        print("-------------")
